Array partition I

Time: O(R); Space: O(R); easy

Given an array of 2n integers, your task is to group these integers into n pairs of integer,

say (a1, b1), (a2, b2), …, (an, bn)

which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: nums = [1,4,3,2]

Output: 4

Explanation:

  • n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Example 2:

Input: nums = [5,6]

Output: 5

Explanation:

  • n is 1, and the maximum sum of pairs is 5 = min(5, 6) .

Constraints:

  • n is a positive integer, which is in the range of [1, 10000].

  • All the integers in the array will be in the range of [-10000, 10000].

Hints:

  1. Obviously, brute force won’t help here. Think of something else, take some example like 1,2,3,4.

  2. How will you make pairs to get the result? There must be some pattern.

  3. Did you observe that- Minimum element gets add into the result in sacrifice of maximum element.

  4. Still won’t able to find pairs? Sort the array and try to find the pattern.

[3]:

class Solution1(object):
    """
    Time: O(R), R is the range size of the integers
    Space: O(R)
    """
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        LEFT, RIGHT = -10000, 10000

        lookup = [0] * (RIGHT-LEFT+1)
        for num in nums:
            lookup[num-LEFT] += 1

        r, result = 0, 0
        for i in range(LEFT, RIGHT+1):
            result += (lookup[i-LEFT] + 1 - r) // 2 * i
            r = (lookup[i-LEFT] + r) % 2

        return result

[4]:

s = Solution1()
nums = [1,4,3,2]
assert s.arrayPairSum(nums) == 4
nums = [5,6]
assert s.arrayPairSum(nums) == 5

[5]:

class Solution2(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        result = 0
        for i in range(0, len(nums), 2):
            result += nums[i]
        return result

[6]:

s = Solution2()
nums = [1,4,3,2]
assert s.arrayPairSum(nums) == 4
nums = [5,6]
assert s.arrayPairSum(nums) == 5

[7]:

class Solution3(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)

        return sum([nums[i] for i in range(0, len(nums), 2)])

[8]:

s = Solution3()
nums = [1,4,3,2]
assert s.arrayPairSum(nums) == 4
nums = [5,6]
assert s.arrayPairSum(nums) == 5